package com.wfm.niuke.dynamic;

import java.util.Arrays;

public class BM65最长公共子序列O095 {
//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    String x = "";
    //获取最长公共子序列
    String ans(int i, int j, int[][] b){
        String res = "";
        //递归终止条件
        if(i == 0 || j == 0)
            return res;
        //根据方向，往前递归，然后添加本级字符
        if(b[i][j] == 1){
            res += ans(i - 1, j - 1, b);
            res += x.charAt(i - 1);
        }
        else if(b[i][j] == 2)
            res += ans(i - 1, j, b);
        else if(b[i][j] == 3)
            res += ans(i,j - 1, b);
        return res;
    }
    public String longestCommonSubsequence(String text1, String text2) {
        x=text1;
        int m =text1.length();
        int n = text2.length();
        int[][] dp = new int[m+1][n+1];
        int[][] b = new int[m+1][n+1];
        for (int j = 0; j < n; j++) {
            dp[0][j]=0;
        }
        for (int i = 0; i < m; i++) {
            dp[i][0]=0;
        }
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n ; j++) {
                if(text1.charAt(i-1)==text2.charAt(j-1)){
                    dp[i][j] = dp[i-1][j-1]+1;
                    b[i][j]=1;
                }else if(dp[i-1][j]>dp[i][j-1]){
                    dp[i][j]=dp[i-1][j];
                    b[i][j]=2;
                }else{
                    dp[i][j]=dp[i][j-1];
                    b[i][j]=3;
                }
            }
        }
//        printTwoNum(dp);
//
//        printTwoNum(b);
        //获取答案字符串
        String res = ans(m,n , b);
        //检查答案是否位空
        if(res.isEmpty())
            return "-1";
        else
            return res;
    }
}
//leetcode submit region end(Prohibit modification and deletion)
    public static void main(String[] args) { 
        Solution solution = new BM65最长公共子序列O095().new Solution();
        System.out.println(solution.longestCommonSubsequence("abcbdab", "bdcaba"));
    }
}